The present invention relates to logic elements for use with programmable logic devices or other similar devices, and to enhancements for such devices specifically to make the implementation of hardware designs containing barrel shifters more efficient.
Programmable logic devices (“PLDs”) (also sometimes referred to as CPLDs, PALs, PLAs, FPLAs, EPLDs, EEPLDs, LCAs, FPGAs, or by other names), are well-known integrated circuits that provide the advantages of fixed integrated circuits with the flexibility of custom integrated circuits. Such devices are well known in the art and typically provide an “off the shelf” device having at least a portion that can be electrically programmed to meet a user's specific needs. Application specific integrated circuits (“ASICs”) have traditionally been fixed integrated circuits, however, it is possible to provide an ASIC that has a portion or portions that are programmable; thus, it is possible for an integrated circuit device to have qualities of both an ASIC and a PLD. The term PLD as used herein will be considered broad enough to include such devices.
PLDs typically include blocks of logic elements, sometimes referred to as logic array blocks (“LABs”; also referred to by other names, e.g., “configurable logic blocks,” or “CLBs”). Logic elements (“LEs”, also referred to by other names, e.g., “logic cells”) may include a look-up table (LUT) or product term, carry-out chain, register, and other elements. LABs also have common control signals which are called “secondary signals.”
Logic elements, including look-up table (LUT)-based logic elements, typically include configurable elements holding configuration data that determines the particular function or functions carried out by the logic element. A typical LUT circuit may include ram bits that hold data (a “1” or “0”). However, other types of configurable elements may be used. Some examples may include static or dynamic random access memory, electrically erasable read-only memory, flash, fuse, and anti-fuse programmable connections. The programming of configuration elements could also be implemented through mask programming during fabrication of the device. While mask programming may have disadvantages relative to some of the field programmable options already listed, it may be useful in certain high volume applications. For purposes herein, the generic term “memory element” will be used to refer to any programmable element that may be configured to determine functions implemented by other PLD.
FIG. 10 illustrates a programmable logic device (PLD) 710 in a data processing system 700. As one example, the described logic circuits may be implemented in logic elements of PLDs such as PLD 710. PLD 710 includes a plurality of logic array blocks (LABs) such as LAB 712 (only one LAB is shown to avoid overcomplicating the drawing). LAB 712 includes a plurality of logic elements such as logic element 711 (only one logic element is shown to avoid overcomplicating the drawing). Data processing system 700 may include one or more of the following components: a processor 740; memory 750; I/O circuitry 720; and peripheral devices 730. These components are coupled together by a system bus 765 and are populated on a circuit board 760 which is contained in an end-user system 770.
System 700 can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD 710 can be used to perform a variety of different logic functions. For example, programmable logic device 710 can be configured as a processor or controller that works in cooperation with processor 740 (or, in alternative embodiments, a PLD might itself act as the sole system processor). PLD 710 may also be used as an arbiter for arbitrating access to a shared resources in system 700. In yet another example, PLD 710 can be configured as an interface between processor 740 and one of the other components in system 700. It should be noted that system 700 is only exemplary.
A typical LUT circuit used as a logic element provides an output signal that is a function of multiple input signals. The particular logic function may be determined by programming the LUT's memory elements. As will be explained further herein (see FIG. 1 and accompanying text), a typical LUT circuit may be represented as a plurality of memory elements coupled to a “tree” of 2:1 muxes. (For compactness of illustration, the muxes shown in FIG. 1 are 4:1 muxes, and the 4:1 muxes include 2:1 muxes.) The LUT mux tree includes a first level comprising a single 2:1 mux providing the LUT output and also includes successive additional levels of muxes, each level including twice as many muxes as the previous level and the number of memory elements being twice as many as the number of 2:1 muxes in a last mux level coupled to the memory elements. Each 2:1 mux level provides a logic input to the LUT circuit coupled to control inputs of the muxes at that mux level. Thus, to obtain an n-input LUT (or “nLUT”) typically requires 2n memory elements and 2n muxes. Adding an input to an nLUT circuit to provide an n+1 input LUT (“(n+1)LUT”) therefore typically requires providing a total of 2n+1 memory elements and (2n+1−1) muxes, i.e., approximately a doubling of resources relative to that required by an nLUT.
For many applications, the functions that need to be implemented by a first LUT circuit and a second LUT circuit are identical. Also, for some applications, it may be possible for inputs of first and second LUT circuits to be shared without reducing the functionality required by the application. In such instances, opportunities are presented that need to be maximized for sharing resources to reduce the total number of memory elements and muxes that would otherwise be required.
Two specific types of functions which can take great advantage of such a method are cross-bar and barrel shifter circuitry. These functions conventionally consume large numbers of logic elements in a programmable logic device, and it would be very advantageous to reduce this logic.
In U.S. patent application Ser. No. 10/351,026 (the '026 application) filed Jan. 24, 2003, a method called “shared LUT mask” or SLM was described to make a more efficient FPGA logic element for logic functions which have large numbers of similar or identical functions. The SLM method works well for crossbars, and for some portions of barrel shifters, but it generally does not obtain further efficiency improvements on barrel shifters. The '026 application is incorporated herein in its entirety.
It would be desirable to apply the SLM method to improve the efficiency of barrel shifters for FPGAs.